import collections


class Solution(object):
    def minRefuelStops(self, target, startFuel, stations):
        st = [startFuel]
        for index, [dist, fuel] in enumerate(stations):
            if index > 0:
                dist = dist - stations[index - 1][0]
            m = len(st)
            node = st[-1]
            if node - dist < 0:
                return -1
            else:
                st.append(node - dist + fuel)
            for i in range(m - 2, -1, -1):
                if st[i] - dist >= 0:
                    new_num = st[i] - dist + fuel
                else:
                    new_num = -1
                if st[i + 1] - dist >= 0:
                    st[i + 1] -= dist
                else:
                    st[i + 1] = -1
                if new_num >= 0:
                    if st[i + 1] >= 0:
                        st[i + 1] = max(new_num, st[i + 1])
                    else:
                        st[i + 1] = new_num
            st[0] = max(st[0] - dist, -1)
        if stations:
            dist = target - stations[-1][0]
        else:
            dist = target
        for i in range(len(st)):
            if st[i] - dist >= 0:
                return i
        return -1


data = Solution()
# target = 100
# startFuel = 10
# stations = [[10, 60], [20, 30], [30, 30], [60, 40]]
# print(data.minRefuelStops(target, startFuel, stations))
# target = 999
# startFuel = 1000
# stations = [[5, 100], [997, 100], [998, 100]]
# print(data.minRefuelStops(target, startFuel, stations))
# target = 100
# startFuel = 25
# stations = [[25, 25], [50, 25], [75, 25]]
# print(data.minRefuelStops(target, startFuel, stations))
target = 1000000
startFuel = 80302
stations = [[52821, 311929], [57329, 447457], [106585, 431610], [404402, 328190], [424591, 285021], [425838, 372155],
            [434324, 103429], [492839, 9269], [493388, 343058], [502052, 196352], [522295, 202890], [555617, 76688],
            [593726, 98030], [617465, 280095], [634894, 205270], [647642, 477117], [658775, 277494], [659802, 153477],
            [673423, 168675], [738516, 10001], [907525, 399694], [916595, 1215], [930008, 373854], [946106, 32543],
            [969696, 70443]]
print(data.minRefuelStops(target, startFuel, stations))
